"""
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

Given two sorted arrays nums1 and nums2 of size m and n respectively, 
return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n))
"""
class Solution(object):
    def findMedianSortedArrays(nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        
        简单方法为：将两个有序表进行合并，之后根据索引找出中位数
        下述方法为：分别一起遍历两个表，count计数，一直遍历到中位数位置
        每次遍历存储旧值和新值，最后根据奇偶数判断返回值。
        """
        m, n = len(nums1), len(nums2)
        sumNum = m + n
        i, j, count = 0, 0, 0
        left, right = 0, 0
        while count <= sumNum //2 :
            if i < m and (j >= n or nums1[i] < nums2[j]) :
                left, right = right, nums1[i]
                i += 1
            else:
                left, right = right, nums2[j]
                j += 1
            count += 1
        if sumNum % 2 == 1:
            return right
        else:
            return (left + right) / 2

